package com.lw.leetcode.back.c;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * 675. 为高尔夫比赛砍树
 *
 * @author liw
 * @version 1.0
 * @date 2022/5/23 9:12
 */
public class CutOffTree {

    public static void main(String[] args) {
        CutOffTree test = new CutOffTree();

        List<List<Integer>> forest = new ArrayList<>();

        // 6
//        forest.add(Arrays.asList(1, 2, 3));
//        forest.add(Arrays.asList(0, 0, 4));
//        forest.add(Arrays.asList(7, 6, 5));

        // -1
//        forest.add(Arrays.asList(1, 2, 3));
//        forest.add(Arrays.asList(0, 0, 0));
//        forest.add(Arrays.asList(7, 6, 5));

        // 6
//        forest.add(Arrays.asList(2, 3, 4));
//        forest.add(Arrays.asList(0, 0, 5));
//        forest.add(Arrays.asList(8, 7, 6));

        // -1
//        forest.add(Arrays.asList(0,0,0,3528,2256,9394,3153));
//        forest.add(Arrays.asList(8740,1758,6319,3400,4502,7475,6812));
//        forest.add(Arrays.asList(0,0,3079,6312,0,0,0));
//        forest.add(Arrays.asList(6828,0,0,0,0,0,8145));
//        forest.add(Arrays.asList(6964,4631,0,0,0,4811,0));
//        forest.add(Arrays.asList(0,0,0,0,9734,4696,4246));
//        forest.add(Arrays.asList(3413,8887,0,4766,0,0,0));
//        forest.add(Arrays.asList(7739,0,0,2920,0,5321,2250));
//        forest.add(Arrays.asList(3032,0,3015,0,3269,8582,0));

        // 57
//        forest.add(Arrays.asList(54581641, 64080174, 24346381, 69107959));
//        forest.add(Arrays.asList(86374198, 61363882, 68783324, 79706116));
//        forest.add(Arrays.asList(668150, 92178815, 89819108, 94701471));
//        forest.add(Arrays.asList(83920491, 22724204, 46281641, 47531096));
//        forest.add(Arrays.asList(89078499, 18904913, 25462145, 60813308));

        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < 50; i++) {
            List<Integer> list = new ArrayList<>();
            for (int j = 0; j < 50; j++) {
                int v = (int) (Math.random() * 10000000);
                while (set.contains(v)) {
                    v = (int) (Math.random() * 10000000);
                    set.add(v);
                }
                list.add(v);
            }
            forest.add(list);
        }
        System.out.println(forest);


        int i = test.cutOffTree(forest);
        System.out.println(i);
    }


    public int cutOffTree(List<List<Integer>> forest) {
        if (forest.get(0).get(0) == 0) {
            return -1;
        }
        int[][] steps = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        int m = forest.size();
        int n = forest.get(0).size();
        int[][][][] items = new int[m][n][m][n];
        int flag = 0;
        int l = m * n;
        long[] sorts = new long[l];
        int index = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                long v = forest.get(i).get(j);
                if (v > 1) {
                    flag++;
                    sorts[index++] = (v << 32) + (i << 16) + j;
                }
            }
        }
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (forest.get(i).get(j) == 0) {
                    continue;
                }
                int f = flag - 2;
                list.add((i << 16) + j );
                int[][] arr = items[i][j];
                arr[i][j] = 1;
                while (!list.isEmpty()) {
                    int poll = list.poll();
                    int x = poll >> 16;
                    int y = poll & 0XFFFF;
                    int c = arr[x][y];
                    for (int[] step : steps) {
                        int a = x + step[0];
                        int b = y + step[1];
                        if (a < 0 || b < 0 || a == m || b == n || arr[a][b] != 0 || forest.get(a).get(b) == 0) {
                            continue;
                        }
                        f--;
                        arr[a][b] = c + 1;
                        list.add((a << 16) + b);
                    }
                }
                if (f > 0) {
                    return -1;
                }
            }
        }
        Arrays.sort(sorts);
        int all = 0;
        int x = 0;
        int y = 0;
        for (int i = 0; i < l; i++) {
            long v = sorts[i];
            if (v == 0) {
                continue;
            }
            int a = ((int) v) >> 16;
            int b = (int) (v & 0XFFFF);
            all += items[x][y][a][b] - 1;
            x = a;
            y = b;
        }
        return all;
    }

}
